{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "12488094",
   "metadata": {},
   "outputs": [],
   "source": [
    "%use fuel(2.3.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c76cec06",
   "metadata": {},
   "outputs": [],
   "source": [
    "val envs = java.io.File(\"../../.env\")\n",
    "    .readLines()\n",
    "    .map {\n",
    "        it.split(\"=\")[0] to it.split(\"=\")[1].trim('\"')\n",
    "    }.toMap()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "90dd77c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "val session = envs.get(\"AOC_SESSION\")\n",
    "val year = 2021\n",
    "val day = 22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6f8e19a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun getInput(year: Int, day: Int, session: String): String {\n",
    "    val (_, _, result) = \"https://adventofcode.com/$year/day/$day/input\"\n",
    "    .httpGet()\n",
    "    .header(\"cookie\" to \"session=$session\")\n",
    "    .responseString()\n",
    "        \n",
    "    return result.get().trim()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7ccb63fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun submitAnswer(year: Int, day: Int, session: String, level: Int, answer: String): String {\n",
    "    val (_, _, result) = Fuel\n",
    "    .post(\n",
    "        \"https://adventofcode.com/$year/day/$day/answer\", \n",
    "        parameters = listOf(\"level\" to level, \"answer\" to answer))\n",
    "    .header(\"cookie\" to \"session=$session\")\n",
    "    .responseString()\n",
    "        \n",
    "    return result.get()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c3a45b88",
   "metadata": {},
   "outputs": [],
   "source": [
    "val sample = \"\"\"on x=10..12,y=10..12,z=10..12\n",
    "on x=11..13,y=11..13,z=11..13\n",
    "off x=9..11,y=9..11,z=9..11\n",
    "on x=10..10,y=10..10,z=10..10\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "353b4ffe",
   "metadata": {},
   "outputs": [],
   "source": [
    "val input = getInput(year, day, session)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5cfc3d7c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class KDNode(val range: List<Pair<Int, Int>>, var state: Boolean) {\n",
    "    var children: List<KDNode> = listOf()\n",
    "    \n",
    "    fun containedBy(range: List<Pair<Int, Int>>): Boolean {\n",
    "        return (0 until range.size).all {\n",
    "            this.range[it].first >= range[it].first && this.range[it].second <= range[it].second\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    fun outsideOf(range: List<Pair<Int, Int>>): Boolean {\n",
    "        return (0 until range.size).any {\n",
    "            this.range[it].first >= range[it].second || this.range[it].second <= range[it].first\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    fun setState(range: List<Pair<Int, Int>>, state: Boolean) {\n",
    "        if (this.outsideOf(range))\n",
    "            return\n",
    "        \n",
    "        if (this.containedBy(range)) {\n",
    "            this.state = state\n",
    "            this.children = listOf()\n",
    "            return\n",
    "        }\n",
    "        \n",
    "        if (this.children.isEmpty()) {\n",
    "            val sub = (0 until range.size).map {\n",
    "                setOf(range[it].first, range[it].second, this.range[it].first, this.range[it].second)\n",
    "                    .filter { i -> i >= this.range[it].first && i <= this.range[it].second }\n",
    "                    .toList()\n",
    "                    .sorted()\n",
    "                    .windowed(2)\n",
    "                    .map { Pair(it[0], it[1]) }\n",
    "                    .toSet()\n",
    "            }\n",
    "                    \n",
    "            this.children = sub.fold(listOf(listOf<Any?>())) { acc, set ->\n",
    "                acc.flatMap { list -> set.map { element -> list + element } }\n",
    "            }.map {\n",
    "                KDNode(it as List<Pair<Int, Int>>, this.state)\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        for (child in this.children)\n",
    "            child.setState(range, state)\n",
    "    }\n",
    "    \n",
    "    fun calc(): Long {\n",
    "        if (this.children.isEmpty()) {\n",
    "            if (this.state) {\n",
    "                var ans = 1L\n",
    "                for (i in 0 until this.range.size)\n",
    "                    ans *= (this.range[i].second - this.range[i].first)\n",
    "                return ans\n",
    "            } else {\n",
    "                return 0L\n",
    "            }\n",
    "        } else {\n",
    "            return this.children.map { it.calc() }.sum()\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "bf8faf25",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun solve(input: String, k: Int, inf: Int): String {\n",
    "    val root = KDNode(buildList { repeat(k) { add(Pair(-inf, inf + 1)) }}, false)\n",
    "        \n",
    "    for (line in input.split(\"\\n\")) {\n",
    "        val state = line[1] == 'n'\n",
    "        val pos = Regex(\"\"\"-?\\d+\"\"\").findAll(line).map { it.groupValues[0].toInt() }.toList()\n",
    "        root.setState(listOf(Pair(pos[0], pos[1] + 1), Pair(pos[2], pos[3] + 1), Pair(pos[4], pos[5] + 1)), state)\n",
    "    }\n",
    "    \n",
    "    return root.calc().toString()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "c0b0db34",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun partOne(input: String): String {\n",
    "    return solve(input, 3, 100)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "8da9fa05",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "39"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partOne(sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "8ebc1855",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "648681"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val partOneAns = partOne(input)\n",
    "partOneAns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92f63c8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "submitAnswer(year, day, session, 1, partOneAns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "6ecbeb07",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun partTwo(input: String): String {\n",
    "    return solve(input, 3, 1000000)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "ca09a766",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "39"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partTwo(sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "24f0ff42",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1302784472088899"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val partTwoAns = partTwo(input)\n",
    "partTwoAns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8a52b614",
   "metadata": {},
   "outputs": [],
   "source": [
    "submitAnswer(year, day, session, 2, partTwoAns)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Kotlin",
   "language": "kotlin",
   "name": "kotlin"
  },
  "language_info": {
   "codemirror_mode": "text/x-kotlin",
   "file_extension": ".kt",
   "mimetype": "text/x-kotlin",
   "name": "kotlin",
   "nbconvert_exporter": "",
   "pygments_lexer": "kotlin",
   "version": "1.6.20-dev-6372"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
